package binarytree

func inorderTraversal(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	res := []int{}

	res = append(res, inorderTraversal(root.Left)...)
	res = append(res, root.Val)
	res = append(res, inorderTraversal(root.Right)...)

	return res
}

func inorderTraversal2(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	res := []int{}

	stack := []*TreeNode{root}
	nodeMap := map[*TreeNode]struct{}{}
	nodeMap[nil] = struct{}{}

	for len(stack) != 0 {
		temp := stack[len(stack)-1]
		_, ok1 := nodeMap[temp.Left]
		if ok1 {
			res = append(res, temp.Val)
			stack = stack[:len(stack)-1]
			if temp.Right != nil {
				stack = append(stack, temp.Right)
			}
			nodeMap[temp] = struct{}{}
		} else {
			stack = append(stack, temp.Left)
		}
	}
	return res
}
